﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>

using namespace std;
 
//学会画图，用数学的方法去思考
// 寻找数组的中?下标（easy）

//int pivotIndex(vector<int>& nums) {
//    int size = nums.size();
//    vector<int> total(size + 1);
//    for (int i = 1; i <= size; i++)
//    {
//        total[i] = total[i - 1] + nums[i - 1];
//    }
//    for (int i = 1; i <= size; i++)
//    {
//        if ((2 * total[i - 1]) + total[i] == total[size])
//            return i - 1;
//    }
//    return -1;
//}
//
//class Solution {
//public:
//    int pivotIndex(vector<int>& nums) {
//        int size = nums.size();
//        vector<int> total(size + 1);
//        for (int i = 1; i <= size; i++)
//        {
//            total[i] = total[i - 1] + nums[i - 1];
//        }
//        for (int i = 1; i <= size; i++)
//        {
//            if ((2 * total[i - 1]) + nums[i - 1] == total[size])
//                return i - 1;
//        }
//        return -1;
//    }
//};

//左右共同求前缀和
//int pivotIndex(vector<int>& nums) {
//    int n = nums.size();
//    vector<int> f(n), g(n);
//    // 预处理前缀和后缀和数组 
//    for (int i = 1; i < n; i++)
//        f[i] = f[i - 1] + nums[i - 1];
//    for (int i = n - 2; i >= 0; i--)
//        g[i] = g[i + 1] + nums[i + 1];
//    // 判断 
//    for (int i = 0; i < n; i++)
//        if (f[i] == g[i]) 
//            return i;
//    return -1;
//}

//矩阵区域和(利用二维数组前缀和)
//class Solution {
//public:
//    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
//        int m = mat.size(), n = mat[0].size();
//        vector<vector<int>> sum(m + 1, vector<int>(n + 1));
//        vector<vector<int>> answer(m, vector<int>(n));
//        for (int i = 1; i < m + 1; i++)
//        {
//            for (int j = 1; j < n + 1; j++)
//                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1];
//        }
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//                answer[i][j] = sum[min(i + k + 1, m)][min(j + k + 1, n)]
//                - sum[min(i + k + 1, m)][max(j - k, 0)] - sum[max(i - k, 0)][min(j + k + 1, n)]
//                + sum[max(i - k, 0)][max(j - k, 0)];
//        }
//        return answer;
//    }
//};

//class Solution {
//public:
//    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
//        int m = mat.size(), n = mat[0].size();
//        vector<vector<int>> sum(m + 1, vector<int>(n + 1));
//        vector<vector<int>> answer(m, vector<int>(n));
//        for (int i = 1; i < m + 1; i++)
//        {
//            for (int j = 1; j < n + 1; j++)
//                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1];
//        }
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            int x2 = min(i + k, m - 1) + 1; int y2 = min(j + k, n - 1) + 1;
//            int x1 = max(i - k, 0) + 1; int y1 = max(0, j - k) + 1;
//            answer[i][j] = sum[x2][y2]
//                - sum[x2][y1 - 1] - sum[x1 - 1][y2]
//                + sum[x1 - 1][y1 - 1];
//        }
//        return answer;
//    }
//};

//位运算（熟练掌握各个位运算的操作）判断字符是否唯⼀（easy）

//class Solution {
//public:
//    bool isUnique(string astr) {
//        int i = 0;
//        for (auto& j : astr)
//        {
//            if (((i >> (j - 'a')) & 1) == 1)
//                return false;
//            i |= 1 << (j - 'a');
//        }
//        return true;
//    }
//};

//#define _CRT_SECURE_NO_WARNINGS 1
//#include<stdio.h>
//#include<stdlib.h>
//#include<time.h>
//#include <cstdlib>
//#include <ctime>
//#include <iostream>
//using namespace std;
//
//struct door
//{
//	int num;
//	bool f;
//};
//
//door a[3];
//bool d(int n)
//{
//	srand(n);
//	int fs = rand() % 3;
//	a[fs].f = true;
//	for (int i = 1; i <= 3; i++)
//	{
//		a[i].num = i;
//		if (i == fs)continue;
//		else a[i].f = false;
//	}
//	int man = rand() % 3;
//	if (a[man].f == true)return false;
//	else return true;
//}
//
//int main()
//{
//	double k = 0;
//	double o = 0;
//	long long n = 10000000;
//	srand(time(NULL));
//	for (long long i = 1; i <= n; i++)
//	{
//		int po = rand() % 10008;
//		if (d(po) == true)k++;
//		else o++;
//	}
//	cout << o / (k + o) << endl;
//	return 0;
//}


//int main()
//{
//    vector<int> nums{ 1, 7, 3, 6, 5, 6 } ;
// 
//    return 0;
//}